def dfs(board,x,y,i,word,visited):
    if board[x][y]!=word[i]:
        return False 
    







































# def dfs(grid,word,i,j,k,visited):
#     m,n=len(grid),len(grid[0])
#     if k==len(word): return True 
#     for d in [(-1,0),(1,0),(0,-1),(0,1)]:
#         newi,newj=i+d[0],j+d[1]
#         if newi>=0 and newi<m and newj>=0 and newj<n and (not visited[newi][newj]) and grid[newi][newj]==word[k]:
#             visited[newi][newj]=True 
#             if dfs(grid,word,newi,newj,k+1,visited): return True
#             visited[newi][newj]=False
#     return False 

# def solve(grid,word):
#     m,n=len(grid),len(grid[0])
#     for i in range(m):
#         for j in range(n):
#             if grid[i][j]==word[0]:
#                 visited=[[False]*n for _ in range(m)]
#                 visited[i][j]=True
#                 if dfs(grid,word,i,j,1,visited): return True 
#     return False 

grid=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCCED"
print(solve(grid,word))

grid=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "SEE"
print(solve(grid,word))

grid=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCB"
print(solve(grid,word))


            